﻿<head>
<link type="text/css" rel="stylesheet" href="http://s.codeproject.com/App_Themes/Std/CSS/CodeProject.min.css?dt=2.3.110329.1">

</head>
<pre>
Title:       Simple Method Caching
Author:      seesharper
Email:       bernhard.richter@gmail.com
Member ID:   2506643
Language:    C#
Platform:    Windows
Technology:  Class Library
Level:       Intermediate
Description: Shows how to create a simple method caching mechanism.
Section      Platforms, Frameworks &amp; Libraries
SubSection   Libraries
License:     CPOL</pre>


<h2>Introduction</h2>
<p>As a developer, chances are that you have looked through your code or the result 
    from the profiler and said ..Ahh this should be cached .. That ought to fix it 
    and before you know it, you have your typical dictionary with a <b>TryGetValue</b> 
    cluttering up your code. </p>
<p>To me, that is just noise in my code and cross cutting concerns, such as 
    caching should be a one liner.<br />
    Preferably it should be a zero liner, but that is a little bit harder to achieve 
    although it most certainly is possible. We take a look at this later on.</p>
<p>So this article is going to demonstrate how to create a simple caching mechanism 
    for deterministic methods.</p>
<h2>Background</h2>

<p>First of all, what makes up a good candidate for caching?
    <br />
    I would say that it depends on how static our data is. In this case we talk 
    about deterministic methods, meaning methods that given the same input they will 
    always produce the same result.<br />
    <br />
    Common sense should tell us that this methods only need to be executed once.
    <br />
    <br />
    It&#39;s like asking the same question twice and we don&#39;t really need to since we 
    already know the answer.<br />
    <br />
    Makes sense, doesn&#39;t it? Only problem is, methods don&#39;t have memory. Yet!!!</p>
<h2>Example</h2>
<p>In order to better show how this all comes together, we need an example.<br />
    </p>
<pre>
public class SampleClass
{
    public int Calculate(int input)
    {
        //Imagine some complex code here 
        //that takes forever to execute.
        return input*2;
    }
}
</pre>
<p>
    Given the input of 2, the result from this method will always be 4.&nbsp; Pretty 
    naive, but still proves the point.</p>
<p>Now how could we optimize this method after reading the devastating numbers in 
    the profile report?</p>
<p>This can be done a number of ways, but I do often see code similar to this:</p>
<pre>
public class SampleClass
{
    private readonly IDictionary&lt;int,int&gt; _cache = new Dictionary&lt;int, int&gt;();
                
    public int Calculate(int input)
    {
        if (!_cache.ContainsKey(input))
        {
            int result = input*2;
            _cache.Add(input,result);
        }
        return _cache[input];
    }
}
</pre>
<p>
    Not very clean, but it takes care of business. That is until the project manager 
    comes up to you and tells you that you can forget about that raise unless you 
    fix that &quot;specified key already exists in the Dictionary&quot; exception. Being an 
    experienced developer you know a threading bug when you see one and maybe you go 
    ahead and add a lock statement.
    <br />
    That way we can make it perform better and at the same time provide a decent 
    level of thread safety.</p>
<p>
&nbsp;Only problem now is that most of the code is all about performance and very 
    little about its actual intention. Noise, is what it is.</p>
<h2>
    Adding memory to methods</h2>
<p>
    It would be nice if the <b>Calculate</b> method had a little memory on its own so that 
    it could just return the correct value given that we provide some known input. 
    (Still we have to imagine here that input * 2 is a very expensive operation.)</p>
<p>
    To be honest, I have never thought of this until I read
    <a href="http://denismarkelov.blogspot.com/2010/12/caching-decorator-for-c-methods.html">
    this</a> blog post by Denis Markelov.</p>
<p>
    His idea is to decorate a method in such a way that it returns a func that 
    points directly back to code not very different from our previous example. 
    Actually here is the whole class that Denis wrote.</p>
<pre>
public static class CacheProvider
{ 
    public static Func&lt;T, TResult&gt; Decorate&lt;T, TResult&gt;(Func&lt;T, TResult&gt; function)
    {
        var cache = new Dictionary&lt;T, TResult&gt;();
        return (x) =&gt;
            {                    
                if (!cache.ContainsKey(x))
                {
                    cache.Add(x, function(x));
                }
                return cache[x];
            };
    }
}</pre>
<p>
    So simple and so brilliant it almost blew my mind.</p>
<p>
    All I did with this code was to make it thread safe using the features in .Net 
    4.0</p>
<pre>
public static class CacheProvider
{        
    public static Func&lt;T,TResult&gt; Decorate&lt;T,TResult&gt;(Func&lt;T,TResult&gt; function)
    {
        var cache = new ConcurrentDictionary&lt;T, TResult&gt;();
        return (arg) =&gt; cache.GetOrAdd(arg, function(arg));
    }
}
</pre>
<p>
    A fully functional caching mechanism with just two lines of code. 
</p>
<p>
    Up until this point I have done nothing but improving Mr.Markelov&#39;s code so that 
    it is thread safe.</p>
<p>
    Let&#39;s just quickly see how we can use this code. 
</p>
<pre>
public class SampleClass
{        
    private Func&lt;int, int&gt; _cachedCalculate;

    public SampleClass()
    {
        _cachedCalculate = CacheProvider.Decorate&lt;int,int&gt;(DoCalculate);
    }

    public int Calculate(int input)
    {
        return _cachedCalculate(input);
    }

    private int DoCalculate(int input)
    {            
        return input*2;                        
    }
}</pre>
<p>
    In the constructor, we create a <b>Func&lt;int,int&gt;</b> that points back to the code 
    inside the <b>CacheProvider</b> itself.</p>
<p>
    Works great, but we are still not down to a one-liner. Further improvements 
    required.</p>
<h2>
    The MethodCache</h2>
<p>
    As we have seen, we still need to deal with some plumbing code to set this up 
    and this can be quite messy if we have a lot of cached methods in our class.</p>
<p>
    We are going to take a look at the code before trying to explain what is does.</p>
<p>
    Here is the code for the <b>MethodCache</b> class.</p>
<pre>
public class MethodCache
{
    private readonly ConcurrentDictionary&lt;Delegate,Delegate&gt; _delegates
        = new ConcurrentDictionary&lt;Delegate, Delegate&gt;();

    public TResult Invoke&lt;T,TResult&gt;(Func&lt;T,TResult&gt; function, T arg)
    {
        return ((Func&lt;T, TResult&gt;) _delegates.GetOrAdd(function, CacheProvider.Decorate(function)))(arg);
    }
}</pre>
<p>
    This is actually sort of a cache itself that keeps a list of decorated methods 
    indexed by the method itself.</p>
<p>
    You might wonder why this class is not static and that is because of the fact 
    that we are storing function delegates and then we are also keeping a strong 
    reference to the target of the delegate.</p>
<p>
    We could get around this by implementing a <b>WeakFunction</b> or something in that 
    direction.
    <br />
    I actually tried that, but things got messy really fast and I wanted this to be 
    as simple as possible.</p>
<p>
    If we go back to our <b>SampleClass</b> we can see this class put to good use.</p>
<pre>
public class SampleClass
{        
    private readonly MethodCache _methodCache = new MethodCache();
        
    public int Calculate(int input)
    {
        return _methodCache.Invoke(DoCalculate, input);
    }

    private int DoCalculate(int input)
    {            
        return input*2;                        
    }
}
</pre>
<p>
    As we can see, the type inference mechanism infers the generic arguments from 
    our target method and we are left with a pretty clean one-liner.
    <br />
    Since the <b>MethodCache</b> is not static, we still need to declare it, but we use the 
    same <b>MethodCache</b> regardless of the number of cached methods in the class.</p>
<h2>
    Multiple Arguments</h2>
<p>
    If we go back to the <b>CacheProvider</b> class we can observe that it stores the 
    return value based on the input value. Quite simple, but this also keeps us from 
    having more that one method argument.</p>
<p>
    I like to keep the number of arguments in my methods as low as possible, but I 
    occasionally create one or two methods that breaks my principle :)</p>
<p>
    Anyhow, since we know are faced with two input values and only one possible key 
    for the dictionary we need to somehow make them appear as one.</p>
<p>
    For this 
    we can use the new <b>Tuple</b> class introduced in .Net 4.0</p>

<p />

    Pretty straight forward and has served me well on a number of occations.<p />

    The CacheProvider&#39;s <b>Invoke</b> method now looks like this for methods acception two 
    arguments.
<pre>
public static Func&lt;T1,T2, TResult&gt; Decorate&lt;T1,T2, TResult&gt;(Func&lt;T1,T2, TResult&gt; function)
{
    var cache = new ConcurrentDictionary&lt;Tuple&lt;T1,T2&gt;, TResult&gt;();
    return (arg1,arg2) =&gt; cache.GetOrAdd(Tuple.Create(arg1,arg2),ck =&gt; function(arg1,arg2));
}
</pre>
<p>
    We draw the the line here at a maximum of 4 arguments. Feel free to extend this 
    although it might be wise to consider if more than 4 arguments is really needed 
    for any method.</p>
<p>
    To use this, you actually just need to copy the 
    <b>CacheProvider</b> and the <b>MethodCache</b> class into your own project and you are good to go.</p>
<p>
    You might want to stop reading here or you could continue as we 
    shift gears into some really cool stuff.<h2>
    Transparent Caching</h2>
<p>
    Previously I mentioned how much I would like to implement caching with as little 
    effort as possible. We are now down to a one-liner, but would it be possible to 
    cache-enable our methods without writing any code at all? And what if we wanted 
    to add caching to a library for which we don&#39;t have the source code?
    <br />
    Is this actually possible?<p>
    Let us step back for a moment and take a look at what we are actually doing to 
    enable caching for any given method.<p>
    This is what we have on our <b>SampleClass</b><pre>
public int Calculate(int input)
{
    return input*2;
}   
</pre>
<p>
    And this is what we need:</p>
<pre>
public int Calculate(int input)
{
    return MethodCache.Invoke(DoCalculate, input);
}

private int DoCalculate(int input)
{
    return input * 2;
}

private MethodCache MethodCache
{
    get { return _methodCache ?? (_methodCache = new MethodCache()); }
}</pre>
<p>
    Lets see what we have done here</p>
<p>First we have created a private property that gives us access to the <b>MethodCache</b> 
    itself</p>
<p>
    Next we have extracted the code from the m the <b>Calculate</b> method into the <b>
    DoCalculate</b> method.</p>
<p>
    Finally we have rewritten the <b>Calculate</b> method so that it now invokes the
    <b>MethodCache.</b></p>
<p>
    Note that the first step is only needed once regardless of the number of cached 
    methods.</p>
<p>
    Sure, we all have those fancy refactoring tools that makes these kind of 
    operations a breeze, but it is a simple and repetitive task. Maybe we could 
    delegate all this tedious method extraction and rewriting to someone else.&nbsp; 
    And while you go.. Ah didn&#39;t we hire some greenhorn fresh out of school the 
    other day?..<br />
    I can tell you that is not whom I&#39;m talking about.</p>
<h2>
    Mono.Cecil</h2>
<p>There are essentially just two tools that lets you emit IL (Intermediate 
    language) instructions into an assembly. The first one is Reflection.Emit and 
    the second one is Mono.Cecil.</p>
<p>
    So why choose the one over the other? The answer to that is really quite simple.
</p>
<p>
    Reflection.Emit can only be used to create new assemblies, while Mono.Cecil has 
    the capability to modify an existing assembly and save it back to disc (or load 
    the modified assembly directly into the app domain)</p>
<p>
    Since we are dealing with an existing assembly here, we need to use Mono.Cecil 
    to accomplish the task.</p>
<p>
    The process of modifying the IL of an assembly is also known as assembly 
    weaving.aving.</p>
<h2>
    The AssemblyWeaver</h2>
<p>
    The <b>AssemblyWeaver</b> class is a simple class that loads an assembly, weaves 
    the target types and saves the modified assembly back to disc.</p>
<p>
    The constructor of the <b>AssemblyWeaver</b> takes two parameter:</p>
<pre>
public AssemblyWeaver(ITypeWeaver typeWeaver, ITypeSelector typeSelector)
{
    Guard.IsNotNull(typeWeaver, "typeWeaver");
    Guard.IsNotNull(typeSelector, "typeSelector");
    _typeWeaver = typeWeaver;
    _typeSelector = typeSelector;
}</pre>
<p>
    The first parameter is an implementation of the <b>ITypeWeaver</b> interface 
    that does the actual weaving of each type.
</p>
<p>
    The second parameter is an implementation of the <b>ITypeSelector</b> interface 
    that is responsible for selecting which types to send to the <b>ITypeWeaver</b>.</p>
<p>
    You might recognize this style of coding as dependency injection.
</p>
<p>
    There are default implementations of both interfaces available an we take a look 
    at both of them.</p>
<h2>
    The ITypeSelector</h2>
<p>
    So the <b>ITypeSelector</b> interface represents a class that is responsible for 
    selecting the types that should be weaved.&nbsp; The interface itself is quite 
    simple.</p>
<pre>
public interface ITypeSelector
{
    /// &lt;summary&gt;
    /// Returns a list of types from the target &lt;paramref name="moduleDefinition"/&gt;. 
    /// &lt;/summary&gt;
    /// &lt;param name="moduleDefinition"&gt;The module that contains the target types.&lt;/param&gt;
    /// &lt;returns&gt;The list of selected types.&lt;/returns&gt;
    IEnumerable&lt;TypeDefinition&gt; Select(ModuleDefinition moduleDefinition);
}
</pre>
<p>
    You can then choose to implement the interface yourself or use the provided 
    implementation.</p>
<p>
    Given that the target assembly is our own and we have the source code for it, we 
    could decorate the target types with an attribute that makes the type eligible 
    for weaving.</p>
<p>
    To help identity the target types and methods, there is a <b>
    EnableMethodCachingAttribute</b> class that is used to decorate types.</p>
<p>
    So we have a <b>AttributeTypeSelector</b> that selects only the types decorated 
    with this attribute.</p>
<pre>
/// &lt;summary&gt;
/// A &lt;see cref="ITypeSelector"/&gt; implementation that selects 
/// types decorated with the &lt;see cref="EnableMethodCachingAttribute"/&gt; 
/// &lt;/summary&gt;
public class AttributeTypeSelector : LambdaTypeSelector
{        
    /// &lt;summary&gt;
    /// Initializes a new instance of the &lt;see cref="AttributeMethodSelector"/&gt; class.
    /// &lt;/summary&gt;
    public AttributeTypeSelector()
        : base(t =&gt;
                    {
                        TypeReference attributeType = t.Module.Import(typeof (EnableMethodCachingAttribute));
                        return t.IsDefined(attributeType);
                    }){}                
}
</pre>
<p>
    As we can see this class inherits from the <b>LambdaTypeSelector</b> class which 
    is a class that selects the target types based on a function delegate.</p>
<pre>
public class LambdaTypeSelector : ITypeSelector
{
    private readonly Func&lt;TypeDefinition, bool&gt; _selector;

    /// &lt;summary&gt;
    /// Initializes a new instance of the &lt;see cref="LambdaTypeSelector"/&gt; class.
    /// &lt;/summary&gt;
    /// &lt;param name="selector"&gt;The function delegate used to select the target types.&lt;/param&gt;
    public LambdaTypeSelector(Func&lt;TypeDefinition,bool&gt; selector)
    {
        _selector = selector;
    }

    /// &lt;summary&gt;
    /// Returns a list of types from the target &lt;paramref name="moduleDefinition"/&gt;. 
    /// &lt;/summary&gt;
    /// &lt;param name="moduleDefinition"&gt;The module that contains the target types.&lt;/param&gt;
    /// &lt;returns&gt;The list of selected types.&lt;/returns&gt;
    public IEnumerable&lt;TypeDefinition&gt; Select(ModuleDefinition moduleDefinition)
    {
        return moduleDefinition.Types.Where(_selector);
    }
}</pre>
<p>
    This class can come in handy if we are weaving assemblies for which we don&#39;t 
    have the source code or that we for some reason don&#39;t want to &quot;clutter&quot; our code 
    with attributes.<br />
</p>
<h2>
    The TypeWeaver</h2>
<p>
    This is the class that actually performs the rewriting of the target types.</p>
<p>
    The <b>TypeWeaver</b> class takes one constructor argument and that is an 
    implementation of the IMethodSelector interface. </p>
<pre>
public TypeWeaver(IMethodSelector methodSelector)        
{
    _methodSelector = methodSelector;
}
</pre>
<p>
    The <b>IMethodSelector</b> implementation is responsible for selecting the methods that 
    are eligible for weaving.</p>
<p>
    There is a default implementation of this interface as well, called the <b>
    AttributeMethodSelector</b> class that works almost in the same way as the 
    <b>AttributeTypeSelector</b> class apart from the fact that we are now looking for the
    <b>CachedAttribute</b> class.
</p>
<p>
    So what we are looking for now are types like this:</p>
<pre>
[EnableMethodCaching]
public class SampleClass
{                
    [Cached]
    public int Calculate(int input)
    {
        return input*2;
    }                
}</pre>
<p>
    Note that the <b>AttributeTypeSelector</b> could be changed into looking at all 
    types that contains at least one method decorated with the <b>CachedAttribute</b>, 
    but that might be a time consuming operation so that is actually the reason for 
    the <b>EnableMethodCachingAttribute</b> in the first place.</p>
<p>
    So what does this <b>TypeWeaver</b> actually do? Well, it should do exactly the 
    same thing as the greenhorn now sitting next to you asking for network 
    credentials.</p>
<ul>
    <li>Create a property the represents the <b>MethodCache</b> instance</li>
    <li>Extract the code in the target method into a new private method.</li>
    <li>Rewrite the target method so that it call the <b>MethodCache.Invoke</b> method</li>
</ul>
<p>
    Now, how hard could it be? Surprisingly is not that difficult, however working 
    with Cecil can be challenging at times. <b>Mono.Cecil</b> is probably one of the most 
    powerful libraries available to the .Net platform, but on the other hand I will 
    put this kindly and say that its documentation is scarse.
</p>
<p>
    When trying to figure out how to emit code it is best to implement what you need 
    in plain C# and then investigate the IL using ildasm.exe.<br />
    Personally I use Reflector or LinqPad to do this, but ildasm will do just fine.</p>
<p>
    So given this code:</p>
<pre>
private MethodCache MethodCache
{
    get
    {
        if (_methodCache == null)
            _methodCache = new MethodCache();
        return _methodCache;
    }
}</pre>
<p>
    This is the IL we need to emit:</p>
<pre>
.property instance class [MethodCaching]MethodCaching.MethodCache Method
{
    .get instance class [MethodCaching]MethodCaching.MethodCache SampleLibrary.TemplateClass::get_Method()
}</pre>
<p>
    The TemplateClass is a class written to have something to reflect over to get 
    the IL.<br />
    Anyway, not much code here and that is because standard CLR properties are 
    just wrappers aroung getter and setter methods, so we need to go to the 
    get_Method to get the actual implementation.</p>
<pre>
.method private hidebysig specialname instance class [MethodCaching]MethodCaching.MethodCache get_Method() cil managed
{
    .maxstack 2
    .locals init (
        [0] class [MethodCaching]MethodCaching.MethodCache cache,
        [1] bool flag)
    L_0000: nop 
    L_0001: ldarg.0 
    L_0002: ldfld class [MethodCaching]MethodCaching.MethodCache SampleLibrary.TemplateClass::_methodCache
    L_0007: ldnull 
    L_0008: ceq 
    L_000a: ldc.i4.0 
    L_000b: ceq 
    L_000d: stloc.1 
    L_000e: ldloc.1 
    L_000f: brtrue.s L_001c
    L_0011: ldarg.0 
    L_0012: newobj instance void [MethodCaching]MethodCaching.MethodCache::.ctor()
    L_0017: stfld class [MethodCaching]MethodCaching.MethodCache SampleLibrary.TemplateClass::_methodCache
    L_001c: ldarg.0 
    L_001d: ldfld class [MethodCaching]MethodCaching.MethodCache SampleLibrary.TemplateClass::_methodCache
    L_0022: stloc.0 
    L_0023: br.s L_0025
    L_0025: ldloc.0 
    L_0026: ret 
}</pre>
<p>That&#39;s more like it. This is exactly the code that we need to emit in order to 
    have a property that returns a <b>MethodCache</b> instance. You can see that there is a 
    lot of IL just to express something that in C# seemed quite simple. As a matter 
    of fact it can be optimized by for instance removing some of the stloc and ldloc 
    instructions that the compiler seems to throw in without any real purpose.
</p>
<p>
    But be careful, if in doubt, emit exactly what ildasm outputs or else you run 
    the risk that the evaluation stack becomes inbalanced and that is defenately not 
    a good thing.
    
    <br />
</p>
<p>
    I am not going to elaborate on the details on how to emit this code using Cecil. 
    It&#39;s pretty straight forward and you find all the IL rewriting code inside the
    <b>TypeWeaver</b> class.</p>
<h2>
    PostWeaving</h2>
<p>
    PostWeaving is a term that is used for assemblies that gets weaved just after 
    they have been compiled.<br />
    So we need something that we can execute from a MSBuild file.
    <br />
    Let us create a simple console application (PostWeaver.exe) to serve this 
    purpose.</p>
<pre>
namespace PostWeaver
{
    class Program
    {
        static void Main(string[] args)
        {
            var assemblyWeaver = new AssemblyWeaver(new TypeWeaver(new AttributeMethodSelector()),
                                                    new AttributeTypeSelector());
            assemblyWeaver.Weave(args[0]);
        }
    }
}
</pre>
<p>
    Next we need to make sure that the PostWeaver.exe gets executed after 
    compilation.
</p>
<p>In our case we are going to postweave the <b>SampleLibrary</b> and we enter the 
    following macro for the
    <br />
    post-build event command line (Project -&gt; Properties -&gt; Build Events)vents)</p>
<pre>&quot;$(SolutionDir)\PostWeaver\bin\$(ConfigurationName)\PostWeaver.exe&quot; &quot;$(TargetPath)&quot;</pre>
<h2>
    Conclusion</h2>
<p>
    Using this tiny library we should be able to take of a lot of our caching needs 
    and no matter if&nbsp; we choose to weave our assemblies or just use the 
    MethodCache directly, it is still pretty simple to use.</p>
<p>
    We have demonstrated how IL rewriting can be used to implement cross cutting 
    concerns.&nbsp; </p>
<p>
    And remember, the fastest way to execute a method is not to execute it at all!!</p>
<h2>
    Points of Interest</h2>

<p><a href="http://plaureano.blogspot.com/2011/04/ndc-talk-preview-ten-simple-rules-for.html">
    NDC Talk Preview: “Ten Simple Rules for Rewriting IL on the Common Language 
    Runtime”</a> by Philip Laureano</p>
<p>A special thanks goes out to Gábor Kozár for teaching me how to create an 
    instance of an generic type with Cecil.</p>
<p>And of course Denis Markelov who got me thinking about this in the first place.</p>

<h2>History</h2>
Initial version 1.0 - Source code host on codeplex
    <a href="http://methodcaching.codeplex.com/">http://methodcaching.codeplex.com/</a></p>


